#pragma once
#include<bits/stdc++.h>	
using namespace std;
class heapSelf {
public:
	int heap_size = 0;
	vector<int> heap;
	heapSelf(vector<int>& nums) {
		heap_size = nums.size();
		heap = nums;
		for (int i = 0; i < heap_size; i++) {
			heapInsert(i);
		}
	}
	void heapInsert(int index) {
		while (heap[(index - 1) / 2] < heap[index])
		{
			swap(heap[(index - 1) / 2], heap[index]);
			index = (index - 1) / 2;
		}
	}
	void heapify(int idex) {
		int left = idex * 2 + 1;
		while (left < heap_size) {
			int largest = left + 1 < heap_size && heap[left + 1] > heap[left] ? left + 1 : left;
			if (heap[idex] >= heap[largest]) {
				break;
			}
			swap(heap[largest], heap[idex]);
			idex = largest;
			left = idex * 2 + 1;
		}
	}
	void heapSort() {
		if (heap_size < 2) return;
		while (heap_size > 0) {
			swap(heap[0], heap[--heap_size]);
			heapify(0);
		}
	}
};